package ACM_Brush;

import java.util.HashMap;
import java.util.Map;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution437 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(-3);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(2);
        root.right.right = new TreeNode(11);
        root.left.left.left = new TreeNode(3);
        root.left.left.right = new TreeNode(-2);
        root.left.right.right = new TreeNode(1);

        int targetSum = 8;
        // System.out.println(new mySolution437().method(root, targetSum));
        System.out.printf("\n%d", new mySolution437().method(root, targetSum));
    }
}

class mySolution437 {
    public int result = 0;

    public int method(TreeNode root, int targetSum) {

        Map<Long, Integer> map = new HashMap<>();
        map.put(0l, 1);
        backTrace(root, map, 0l, targetSum);
        return result;
    }

    private void backTrace(TreeNode root, Map<Long, Integer> map, long pre, int targetSum) {
        if (root == null)
            return;
        pre += root.val;
        if (map.containsKey(pre - targetSum)) {
            result += map.get(pre - targetSum);
        }
        if (map.containsKey(pre))
            map.put(pre, map.get(pre) + 1);
        else
            map.put(pre, 1);
        backTrace(root.left, map, pre, targetSum);
        backTrace(root.right, map, pre, targetSum);

        if (map.get(pre) == 1)
            map.remove(pre);
        else
            map.put(pre, map.get(pre) - 1);
    }
}